#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/6/20 18:22
# ===========================================
#       题目名称： 45. 跳跃游戏 II
#       题目地址： https://leetcode.cn/problems/jump-game-ii/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    def jump(self, nums):
        """
        给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
    每个元素 nums[i] 表示从索引 i 向前跳转的<b>最大长度</b>。换句话说，如果你在 nums[i] 处，
    你可以跳转到任意 nums[i + j] 处:
        0 <= j <= nums[i] 
        i + j < n
    返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

            最小跳跃数
         val   2,3,1,1,4
         index 0,1,2,3,4
               2
                    4
                    越界 jump = 2
        """
        jump = 0  # 初始跳跃次数
        start, end = 0, 1  # 定义起始位置
        while end < len(nums):
            max_val = 0
            for cur_index in range(start, end):
                max_val = max(max_val, cur_index + nums[cur_index])
            start = end
            end = max_val + 1
            jump += 1

        return jump


if __name__ == '__main__':
    s = Solution()
    print("nums = [2,3,1,1,4]=>", s.jump(nums=[2, 3, 1, 1, 4]))  # 2
    print("nums = [2,3,0,1,4]=>", s.jump(nums=[2, 3, 0, 1, 4]))  # 2
    print("nums = [1,2]=>", s.jump(nums=[1, 2]))  # 1
    print("nums = [1,2,3]=>", s.jump(nums=[1, 2, 3]))  # 1
    print("nums = [1,1,1,1]=>", s.jump(nums=[1, 1, 1, 1]))  # 3